package main

import (
	"math"
	"sort"
)

// 16. 最接近的三数之和
func main() {
	println(threeSumClosest([]int{-1, 2, 1, -4}, 1))
}

func threeSumClosest(nums []int, target int) int {
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	i := 0
	closest := math.MaxInt64
	for i < len(nums)-1 {
		if i > 0 && nums[i] == nums[i-1] {
			i++
			continue
		}
		towClosest := towSumClosest(nums[i+1:], target-nums[i])
		if math.Abs(float64(closest-target)) > math.Abs(float64(towClosest+nums[i]-target)) {
			closest = towClosest + nums[i]
		}
		i++
	}
	return closest
}

func towSumClosest(nums []int, target int) int {
	i := 0
	j := len(nums) - 1
	towClosest := math.MaxInt64
	for i < j {
		if i > 0 && nums[i] == nums[i-1] {
			i++
			continue
		}
		if nums[i]+nums[j] == target {
			return target
		} else {
			if math.Abs(float64(towClosest-target)) > math.Abs(float64(nums[i]+nums[j]-target)) {
				towClosest = nums[i] + nums[j]
			}
			if nums[i]+nums[j] < target {
				i++
			} else if nums[i]+nums[j] > target {
				j--
			}
		}
	}
	return towClosest
}
